package btree;

import java.util.*;
import java.util.concurrent.LinkedBlockingDeque;

public class Demo2 {
    public static void main(String[] args) {
        new Demo2().test();
    }

    public void test() {
        long ll = 111l;
        final int[] a = new int[] {123, 423, 1, 2, 3, 5, 7, 15, 16, 29, 20, 34, 53, 56};
        Node<Integer> root = new Node<>(0);
        Queue<Node<Integer>> q = new LinkedBlockingDeque<>((int)Math.pow(2, a.length));
        q.add(root);
        for (int i = 0; i < a.length; i++) {
            int size = q.size();
            for (int j = 0; j < size; j++) {
                Node<Integer> poll = q.poll();
                Node<Integer> left = new Node<>(0);
                Node<Integer> right = new Node<>(a[i]);
                poll.setLeft(left);
                poll.setRight(right);

                left.parent = poll;
                right.parent = poll;
                q.add(left);
                q.add(right);
            }
        }
        viewBTree(root, 15);
    }

    public <T> T[] viewBTree(Node<T> root, int sum) {
        Stack<Node<T>> s = new Stack<>();
        Node<T> p = root;
        List<T> list = new ArrayList<>();
        do {
            int _sum = 0;
            Node<T> temp = p;
            list.clear();
            while (temp != null) {
                _sum += (Integer)temp.data;
                list.add(temp.data);
                temp = temp.parent;
            }
            boolean stop = false;
            if (sum == _sum) {
                for (int i = list.size() - 1; i >= 0; i--) {
                    System.out.print(list.get(i).toString().length() == 1 ? " " + list.get(i) + ", " : list.get(i) + ", ");
                }
                System.out.println();
                stop = true;
            }
            else if (_sum > sum) {
                stop = true;
            }

            if (p.left != null && !stop) {
                s.add(p);
                p = p.left;
                continue;
            }
            if (p.right != null && !stop) {
                p = p.right;
                continue;
            }
            Node<T> top = null;
            while (!s.empty() && (top = s.pop()) != null && top.right == null) {
            }
            if (top == null) {
                break;
            }
            p = top.right;
        } while (true);
        return null;
    }

    public String lpad(String str) {
        return "";
    }
    public <T> void showSequence(Stack<Node<T>> s) {
        s.forEach((item) -> {
            System.out.print(item.data);
        });
        System.out.println();
    }

    class Node<T> {
        public T data;
        public Node<T> left;
        public Node<T> right;
        public Node<T> parent;

        public Node<T> setLeft(Node<T> node) {
            this.left = node;
            return this;
        }
        public Node<T> setRight(Node<T> node) {
            this.right = node;
            return this;
        }

        public Node(){}
        public Node(T data){
            this.data = data;
        }
    }
}
